<!DOCTYPE html>
<html lang="zh-cn">

<head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">

    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <meta name="description" content="ssdut dsa web" />
    <meta name="author" content="" />

    <title>ssdut.DSA/图/网络最大流</title>
    <link rel="stylesheet" href="../assets/css/fonts/linecons/css/linecons.css">
    <link rel="stylesheet" href="../assets/css/fonts/fontawesome/css/font-awesome.min.css">
    <link rel="stylesheet" href="../assets/css/bootstrap.css">
    <link rel="stylesheet" href="../assets/css/xenon-core.css">
    <link rel="stylesheet" href="../assets/css/xenon-forms.css">
    <link rel="stylesheet" href="../assets/css/xenon-components.css">
    <link rel="stylesheet" href="../assets/css/xenon-skins.css">
    <link rel="stylesheet" href="../assets/css/custom.css">
    <link rel="stylesheet" type="text/css" href="../assets/css/stylesheet.css">
    <link rel="stylesheet" type="text/css" href="../assets/css/common.css">
    <link rel="stylesheet" href="../assets/css/viz-1.0.1.css">
    <link rel="stylesheet" href="../assets/css/visual.css">
    <link rel="stylesheet" href="../assets/css/drawgraph.css">


    <script src="../assets/js/jquery-3.3.1.min.js"></script>

</head>

<body class="page-body">
    <div class="page-container">
        <!-- add class"sidebar-collapsed" to close sidebar by default,"chat-visible" to make chat appear always -->

        <!-- Add"fixed" class to make the sidebar fixed always to the browser viewport. -->
        <!-- Adding class"toggle-others" will keep only one menu item open at a time. -->
        <!-- Adding class"collapsed" collapse sidebar root elements and show only icons. -->
        <div class="sidebar-menu toggle-others fixed">

            <div class="sidebar-menu-inner">

                <header class="logo-env">
                    <!-- logo -->
                    <div class="logo">
                        <a href="../" class="logo-expanded">
                            <img src="../assets/images/logo@2x.png" width="80" alt="" />
                        </a>

                        <a href="../" class="logo-collapsed">
                            <img src="../assets/images/logo-collapsed@2x.png" width="40" alt="" />
                        </a>
                    </div>
                 
                </header>
                <ul id="main-menu" class="main-menu">
                    <!-- add class"multiple-expanded" to allow multiple submenus to open -->
                    <!-- class"auto-inherit-active-class" will automatically add"active" class for parent elements who are marked already with class"active" -->
                    <li >
                        <a href="../index.html">
                            <i class="fa-home"></i>
                            <span class="title">首页</span>
                        </a>
                    </li>
                    <li>
                        <a href="../list/ll.html">
                            <i class="fa-chain"></i>
                            <span class="title">线性表</span>
                        </a>
                        <ul>
                            <li>
                                <a href="../list/ll.html">
                                    <span class="title">单链表</span>
                                </a>
                            </li>
                            <li>
                                <a href="../list/stack.html">
                                    <span class="title">栈</span>
                                </a>
                            </li>
                            <li>
                                <a href="../list/queue.html">
                                    <span class="title">队列</span>
                                </a>
                            </li>
                            <li>
                                <a href="../list/dll.html">
                                    <span class="title">双向链表</span>
                                </a>
                            </li>
                            <li>
                                <a href="../list/deque.html">
                                    <span class="title">双端队列</span>
                                </a>
                            </li>

                        </ul>
                    </li>
                    <li>
                        <a href="../tree/bst.html">
                            <i class="fa-sitemap"></i>
                            <span class="title">二叉树</span>
                        </a>
                        <ul>
                            <li>
                                <a href="../tree/bst.html">
                                    <span class="title">二叉搜索树</span>
                                </a>
                            </li>
                            <li>
                                <a href="../tree/avl.html">
                                    <span class="title">平衡二叉搜索树</span>
                                </a>
                            </li>
                            <li>
                                <a href="../tree/heap.html">
                                    <span class="title">堆</span>
                                </a>
                            </li>
                        </ul>
                    </li>
                    <li class="opened active">
                        <a href="../graph/graphds.html">
                            <i class="fa-share-alt"></i>
                            <span class="title">图</span>
                        </a>
                        <ul>
                            <li>
                                <a href="../graph/graphds.html">
                                    <span class="title">图的数据结构</span>
                                </a>
                            </li>
                            <li>
                                <a href="../graph/dfsbfs.html">
                                    <span class="title">图的遍历</span>
                                </a>
                            </li>
                            <li>
                                <a href="../graph/mst.html">
                                    <span class="title">最小生成树</span>
                                </a>
                            </li>
                            <li>
                                <a href="../graph/sssp.html">
                                    <span class="title">最短路径</span>
                                </a>
                            </li>
                            <li class="active">
                                <a href="../graph/maxflow.html">
                                    <span class="title">网络最大流</span>
                                </a>
                            </li>
                        </ul>
                    </li>
                    <li>
                        <a href="../hashtable/lp.html">
                            <i class="fa-random"></i>
                            <span class="title">散列表</span>                          
                        </a>
                        <ul>
                            <li>
                                <a href="../hashtable/lp.html">
                                    <span class="title">线性探查</span>
                                </a>
                            </li>
                            <li>
                                <a href="../hashtable/qp.html">
                                    <span class="title">二次探查</span>
                                </a>
                            </li>
                            <li>
                                <a href="../hashtable/dh.html">
                                    <span class="title">双散列</span>
                                </a>
                            </li>
                            <li>
                                <a href="../hashtable/sc.html">
                                    <span class="title">分离链接</span>
                                </a>
                            </li>
                        </ul>
                    </li>
                    <li >
                        <a href="../sorting/bubble.html" >
                            <i class="fa-sort-amount-asc"></i>
                            <span class="title">排序</span>
                        </a>
                        <ul>
                            <li>
                                <a href="../sorting/bubble.html">
                                    <span class="title">冒泡排序</span>
                                </a>
                            </li>
                            <li>
                                <a href="../sorting/selection.html">
                                    <span class="title">选择排序</span>
                                </a>
                            </li>
                            <li>
                                <a href="../sorting/insertion.html">
                                    <span class="title">插入排序</span>
                                </a>
                            </li>
                            <li>
                                <a href="../sorting/merge.html">
                                    <span class="title">归并排序</span>
                                </a>
                            </li>
                            <li>
                                <a href="../sorting/quick.html">
                                    <span class="title">快速排序</span>
                                </a>
                            </li>
                            <li >
                                <a href="../sorting/radix.html" >
                                    <span class="title">基数排序</span>
                                </a>
                            </li>
                        </ul>
                    </li>             
                </ul>
            </div>
        </div>

        <div class="main-content">

            <!-- User Info, Notifications and Menu Bar -->
          
                <div class="row" style="margin:-30px -30px 0 -30px; background-color: #FFF; padding:15px 10px 10px; ">
                    <div class="col-auto">
                        <ul class="user-info-menu left-links list-inline list-unstyled">
                            <li class="hidden-sm hidden-xs">
                                <a href="#" data-toggle="sidebar">
                                    <i class="fa-bars"></i>
                                </a>
                            </li>
                        </ul>        
                    </div>
                    <!-- Left links for user info navbar -->
                    <div class="col-auto">
                        <h4 id="page-title" >链表</h4>
                    </div>
                    <div class="col-auto me-auto">
                        <div id="current-action" ></div>
                    </div>               
                    <div class="col-auto" >
                                    <!-- Right links for user info navbar -->              
                        <div id="speed-control">
                            减速
                            <div id="speed-input" class="ui-slider ui-corner-all ui-slider-horizontal ui-widget ui-widget-content">
                                <span tabindex="0" class="ui-slider-handle ui-corner-all ui-state-default" style="left: 72.2222%;"></span>
                            </div>
                            加速
                        </div>              
                    </div>
                </div>
            

            <script type="text/javascript">
                jQuery(document).ready(function($) {     
                    // Charts
                    var xenonPalette = ['#68b828', '#7c38bc', '#0e62c7', '#fcd036', '#4fcdfc', '#00b19d', '#ff6264', '#f7aa47'];
                    // Pageviews Visitors Chart
                  
                      
                     
                    $("#page-title").text('最大流');
                });             
                
            </script>

            <div class="row">

              
                <div id="dark-overlay"></div>


                <div id="viz">

                </div>
                

                <div id="overlay" hidden="" style="opacity: 0; display: none;"></div>


                <div id="popup" hidden="">
                    <div id="popup-content"></div>
                    <span id="hide-popup" hidden="" style="background-color: rgb(255, 138, 39);">X <u>关闭</u></span>
                </div>
         

                <script>
                    var PHP_DOMAIN ="";

                    // surprise colour!
                    // Referenced to in  home.js and viz.js also
                    var colourArray = ["#52bc69","#d65775" /*"#ed5a7d"*/ ,"#2ebbd1","#d9513c","#fec515","#4b65ba","#ff8a27","#a7d41e"]; // green, pink, blue, red, yellow, indigo, orange, lime

                    function disableScroll() {
                        $('html').css('overflow', 'hidden');
                    }

                    function enableScroll() {
                        $('html').css('overflow', 'visible');
                    }

                    function replaceAll(find, replace, str) {
                        return str.replace(new RegExp(find, 'g'), replace);
                    }

                    function getColours() {
                        var generatedColours = new Array();
                        while (generatedColours.length < 4) {
                            var n = (Math.floor(Math.random() * colourArray.length));
                            if ($.inArray(n, generatedColours) == -1)
                                generatedColours.push(n);
                        }
                        return generatedColours;
                    }

                    function isOn(value, position) {
                        return (value >> position) & 1 === 1;
                    }

                    function customAlert(msg) {
                        $('#custom-alert p').html(msg);
                        var m = -1 * ($('#custom-alert').outerHeight() / 2);
                        $('#custom-alert').css('margin-top', m + 'px');
                        $('#dark-overlay').fadeIn(function() {
                            $('#custom-alert').fadeIn(function() {
                                setTimeout(function() {
                                    $('#custom-alert').fadeOut(function() {
                                        $('#dark-overlay').fadeOut();
                                    });
                                }, 1000);
                            });
                        });
                    }

                    function showLoadingScreen() {
                        $('#loading-overlay').show();
                        $('#loading-message').show();
                    }

                    function hideLoadingScreen() {
                        $('#loading-overlay').hide();
                    }

                    function commonAction(retval, msg) {
                        //setTimeout(function() {
                        if (retval) { // mode =="exploration" && // now not only for exploration mode, but check if this opens other problems
                         
                            $('#current-action').html(mode =="exploration" ? msg : ("e-Lecture Example (auto play until done)<br>" + msg));
                            $('#progress-bar').slider("option","max", gw.getTotalIteration() - 1);
                            triggerRightPanels();
                            isPlaying = true;
                        }
                        //}, 500);
                    }

                    function getQueryVariable(variable) {
                        var query = window.location.search.substring(1);
                        var vars = query.split('&');
                        for (var i = 0; i < vars.length; i++) {
                            var pair = vars[i].split('=');
                            if (decodeURIComponent(pair[0]) == variable)
                                return decodeURIComponent(pair[1]);
                        }
                        return"";
                    }

                    var generatedColours = getColours();
                    var surpriseColour = colourArray[generatedColours[0]];
                    var colourTheSecond = colourArray[generatedColours[1]];
                    var colourTheThird = colourArray[generatedColours[2]];
                    var colourTheFourth = colourArray[generatedColours[3]];

                    $(function() {
                       

                        // title
                        $('#title a').click(function() {
                            $('#title a').removeClass('selected-viz');
                            $(this).addClass('selected-viz');
                            // temporary quick fix for Google Chrome Aug 2016 issue...
                            setTimeout(function() {
                                document.body.style.zoom ="100.1%";
                            }, 100); // force resize/redraw...
                            setTimeout(function() {
                                document.body.style.zoom ="100%";
                            }, 600);
                        });

                        // overlays stuffs
                        $('#trigger-about').click(function() {
                            if ($(window).width() > 600) {
                                $('#dark-overlay').fadeIn(function() {
                                    $('#about').fadeIn();
                                });
                            } else
                                alert('Sorry, this dialog is too big. Please load it on bigger screen');
                        });

                        $('#trigger-team').click(function() {
                            if ($(window).width() > 600) {
                                $('#dark-overlay').fadeIn(function() {
                                    $('#team').fadeIn();
                                });
                            } else
                                alert('Sorry, this dialog is too big. Please load it on bigger screen');
                        });

                        $('#trigger-terms').click(function() {
                            if ($(window).width() > 600) {
                                $('#dark-overlay').fadeIn(function() {
                                    $('#termsofuse').fadeIn();
                                });
                            } else
                                alert('Sorry, this dialog is too big. Please load it on bigger screen');
                        });

                        $('.close-overlay').click(function() {
                            $('.overlays').fadeOut(function() {
                                $('#dark-overlay').fadeOut();
                            });
                        });

                        $('#dark-overlay').click(function() {
                            $('.overlays').fadeOut();
                            $('#dark-overlay').fadeOut();
                        });
                    });
                </script>




                <script>
                    window.onpopstate = function(event) {
                        var slide = event.state['slide'];
                        openSlide(slide, function() {
                            runSlide(slide);
                        });
                    };

                    function getUrlParameter(sParam) {
                        var sPageURL = decodeURIComponent(window.location.search.substring(1)),
                            sURLVariables = sPageURL.split('&'),
                            sParameterName, i;

                        for (i = 0; i < sURLVariables.length; i++) {
                            sParameterName = sURLVariables[i].split('=');
                            if (sParameterName[0] === sParam) return sParameterName[1] === undefined ? true : sParameterName[1];
                        }
                    };

                    function pushState(slideValue) {
                        var url = '/zh/list';
                        if (typeof slideValue != 'undefined' && slideValue != null) url += '?slide=' + slideValue;
                        window.history.pushState({
                            slide: slideValue
                        },"slide" + slideValue, url);
                    }

                    function showPopup(callback) {
                        $('#popup').fadeIn(100, callback);
                    }

                    function hidePopup(callback) {
                        $('#popup').fadeOut(100, callback);
                    }

                    $(function() {
                        var slide = getUrlParameter('slide');

          

                        $('.mcq-submit').click(function() {
                            var questionId = parseInt($(this).attr('id').split('-')[1]);
                            var answer = $('#mcq-answer-' + questionId).val();
                            var userAnswer = $('input[type=radio][name=mcq-' + questionId + '-choice]:checked').val();

                            if (answer === userAnswer) {
                                $('#answer-status-' + questionId).html('<font color="green"><b>Correct!</b></font>');
                            } else {
                                $('#answer-status-' + questionId).html('<font color="red"><b>Wrong Answer! Try again...</b></font>');
                            }
                            $('#answer-status-' + questionId).show();
                            setTimeout(function() {
                                $('#answer-status-' + questionId).fadeOut(1000);
                            }, 1000);
                        });

                        $('.msq-submit').click(function() {
                            var questionId = parseInt($(this).attr('id').split('-')[1]);
                            var answer = $('#msq-answer-' + questionId).val();

                            var answers = [];
                            $('input[type=checkbox][class=msq-choice]:checked').each(function() {
                                answers.push($(this).attr('id').split('-')[3]);
                            });
                            answers.sort();
                            var userAnswer = answers.join(',');

                            if (answer === userAnswer) {
                                $('#answer-status-' + questionId).html('<font color="green">Correct!</font>');
                            } else {
                                $('#answer-status-' + questionId).html('<font color="red">Wrong Answer! Try again...</font>');
                            }
                            $('#answer-status-' + questionId).show();
                            setTimeout(function() {
                                $('#answer-status-' + questionId).fadeOut(1000);
                            }, 1000);
                        });

                      

                        $('#hide-popup').click(function() {
                            hidePopup();
                        });

                        $('#popup').hover(function() {
                            $('#hide-popup').show();
                        }, function() {
                            $('#hide-popup').hide();
                        });




                        // temporary quick fix for Google Chrome Aug 2016 issue..., put at last part so that everything else has been loaded
                        // setTimeout(function(){ document.body.style.zoom ="100.1%"; }, 500);
                        // setTimeout(function(){ document.body.style.zoom ="100%"; }, 600);
                        // I turn it off on 14 June 2018, seems 'ok'?
                    });

               

                    function adjustPopupToImageSize() {
                        var width = $('#popup-image').prop('width');
                        var height = $('#popup-image').prop('height');
                        $('#popup').width(width + 20);
                        $('#popup').height(height + 20);
                        if (width == 0 && height == 0) {
                            setTimeout(adjustPopupToImageSize, 200);
                        } else {
                            showPopup();
                        }
                    }

                    function POPUP_IMAGE(url) {
                        $('#popup-content').html('<img id="popup-image" src="' + url + '">');
                        adjustPopupToImageSize();
                    }

                    function URL(url) {
                        window.open(url, '_blank');
                    }

                </script>


            </div>






            <!-- Main Footer -->
            <!-- Choose between footer styles:"footer-type-1" or"footer-type-2" -->
            <!-- Add class"sticky" to  always stick the footer to the end of page (if page contents is small) -->
            <!-- Or class"fixed" to  always fix the footer to the end of page -->
            <footer class="main-footer sticky footer-type-2 sticky fixed">

                <div class="footer-inner">
                    <div class="row">
                        <div class="col-auto">
                            <div class="btn-group dropdown dropup">                               
                                <a id="actions-toggle" class="btn btn-sm btn-info dropdown-toggle " data-bs-toggle="dropdown"  data-bs-auto-close="outside" aria-haspopup="true" aria-expanded="false">                            
                                    操作                                                      
                                </a>                                    
                                <div id="actions" class="dropdown-menu">
                                    <div class="dropdown dropend">
                                        <a id="search" class="dropdown-item " onclick="drawGraph()" >
                                            绘制图</a>                                        
                                    </div>
                                    <div class="dropdown dropend">                                        
                                        <a id="create" class="dropdown-item dropdown-toggle" href="#"_id="dropdown-create" data-bs-toggle="dropdown" aria-haspopup="true" aria-expanded="false">创建</a>
                                        <div class="dropdown-menu" aria-labelledby="dropdown-create">
                                            <div class="dropdown-item" onclick="example(CP3_4_24);" >
                                                <a>有向图1</a>
                                            </div>
                                            <div class="dropdown-item" onclick="example(CP3_4_26_1);">
                                                <a>有向图2</a>
                                            </div>
                                            <div class="dropdown-item" onclick="example(CP3_4_26_2);">
                                                <a>有向图3</a>
                                            </div>
                                            <div class="dropdown-item" onclick="example(CP3_4_26_3);" >
                                                <a>有向图4</a>
                                            </div>
                                            <div class="dropdown-item" onclick="example(FORDFULKERSON_KILLER);" >
                                                <a>不适用福特-福克森算法的图</a>
                                            </div>
                                            <div class="dropdown-item" onclick="example(DINIC_SHOWCASE);" >
                                                <a>适用广度优先的有向图</a>
                                            </div>          
                                          
                                                         
                                        </div>
                                    </div>
                                    
                                
                                    <div class="dropdown dropend">
                                        <a id="insert" class="dropdown-item dropdown-toggle" href="#"_id="dropdown-insert" data-bs-toggle="dropdown" aria-haspopup="true"   aria-expanded="false">
                                            最大流算法</a>
                                        <div class="dropdown-menu " aria-labelledby="dropdown-insert" style="min-width: 200px;">
                                            <div  class="dropdown-item-text" >
                                                起始结点 <input type="number" id="sourcevertex" title="Enter an Integer" autocomplete="off" min="0" max="99" value="0">
                                            </div>   
                                            <div  class="dropdown-item-text" >
                                                结束结点 <input type="number" id="sinkvertex" title="Enter an Integer" autocomplete="off" min="0" max="99" value="3">
                                            </div>  
                                            <div class="dropdown-divider" ></div>
                                            <div class="dropdown-item"  onclick="countmaxflow('fordfulkerson');">
                                                福特-福克森算法                                                                                
                                            </div>                                           
                                        </div>  
                                    </div>
                                </div>
                            </div>
                        </div>
                        
                        <div class="col-auto">
                            <span id="go-to-beginning" class="media-control-button" title="go to beginning" onclick="goToBeginning()"><img
                                src="../assets/images/goToBeginning.png" alt="go to beginning"></span>
                        </div>
                        <div class="col-auto">
                            <span id="previous" class="media-control-button" title="step backward" onclick="stepBackward()"><img
                                src="../assets/images/prevFrame.png" alt="previous frame"></span>
                        </div>
                        <div class="col-auto">
                            <span id="pause" class="media-control-button" title="pause" onclick="pause()" ><img
                                src="../assets/images/pause.png" alt="pause"></span>
                            <span id="play" class="media-control-button" title="play" onclick="play()" style="display: none;">
                                <img src="../assets/images/play.png" alt="play"></span>
                        </div>
                        <div class="col-auto">
                            <span id="next" class="media-control-button" title="step forward" onclick="stepForward()"><img
                                src="../assets/images/nextFrame.png" alt="next frame"></span>
                        </div>
                        <div class="col-auto">
                            <span id="go-to-end" class="media-control-button" title="go to end" onclick="goToEnd()"><img
                                src="../assets/images/goToEnd.png" alt="go to end"></span>
                        </div>


                        <div class="col-5 me-auto">
                            <div id="progress-bar" class="slider ui-slider ui-slider-horizontal ui-widget ui-widget-content ui-corner-all" data-min="0" data-max="1800" data-value="223">
                            </div>

                        </div>
                        <div class="col-auto">
                            <div class="btn-group dropdown dropup">
                                <a id="codetrace-toggle" class="btn btn-sm btn-warning dropdown-toggle" data-bs-toggle="dropdown" data-bs-auto-close="false" aria-expanded="false" data-bs-offset="0,20">                            
                                    代码跟踪
                                                  
                                </a>
                                <div id="codetrace-panel" class="dropdown-menu dropdown-menu-end">
                                    <div class="row" style="width: 600px;">
                                        <div class="col-sm-12">
                                            <div id="status" class=" col-sm-12" >
                                                <p></p>
                                            </div>
                                            <div id="codetrace" class=" col-sm-12">
                                                <p id="code1" style="padding-top: 10px; background-color: rgb(82, 188, 105); color: rgb(255, 255, 255);"></p>
                                                <p id="code2" style="background-color: rgb(82, 188, 105); color: rgb(255, 255, 255);"></p>
                                                <p id="code3" style="background-color: rgb(82, 188, 105); color: rgb(255, 255, 255);"></p>
                                                <p id="code4" style="background-color: rgb(82, 188, 105); color: rgb(255, 255, 255);"></p>
                                                <p id="code5" style="background-color: rgb(82, 188, 105); color: rgb(255, 255, 255);"></p>
                                                <p id="code6" style="background-color: rgb(82, 188, 105); color: rgb(255, 255, 255);"></p>
                                                <p id="code7" style="padding-bottom: 10px; background-color: rgb(82, 188, 105); color: rgb(255, 255, 255);"></p>
                                            </div>
                                        </div>
                                    </div>
                                </div>

                            </div>
                        </div>
                     </div>  
            </footer>
        </div>
    </div>    

    <div class="page-loading-overlay">
        <div class="loader-2"></div>
    </div>

    <div id="drawgraph" class="overlays" style="display: none;">  
        <script>var JSONresult;</script>    
        <div id="main">      
            <div id="draw-status">
                <p>绘制具有不同属性的图，然后尝试在其图上运行各种图的遍历算法。
                    <div>默认绘图模式是有向图（每个边有一个或最多两个箭头）。
                </div>
            </p>
        </div>      
        <div id="draw-warn"><p>没有警告</p></div>      
        <div id="draw-err"><p>没有错误</p></div>      
        <div id="viz">        
            <svg onclick="GraphVisu(false,true,null,null,null,true); " width="640" height="360">
                 
            </svg>    
        </div>    
            <div id="drawgraph-actions">      
                <p onclick="drawCancel()">取消绘制</p>      
                <p onclick="GraphVisu(false,true,true)">消除</p>      
                <p onclick="drawDone()">绘制完成</p>      
                <form id="drawgraph-form">        
                    <!--<input type="checkbox" id="submit" name="submit" value="submit" checked="checked">Submit drawn graph to database for random graph and online quiz purposes        <br>-->
                    <input type="checkbox" id="copy" name="submit" value="submit">导出到剪贴板      
                </form>    
            </div>  
        </div>
    </div>


    <!-- Bottom Scripts -->
    <script src="../assets/js/bootstrap.bundle.js"></script>
    <script src="../assets/js/bootstrap5.dropdown.ml.hack.js"></script>
    <script src="../assets/js/TweenMax.min.js"></script>
    <script src="../assets/js/resizeable.js"></script>
    <script src="../assets/js/joinable.js"></script>
    <script src="../assets/js/xenon-api.js"></script>
    <script src="../assets/js/xenon-toggles.js"></script>


    <!-- Imported scripts on this page -->
    <script src="../assets/js/xenon-widgets.js"></script>
    <script src="../assets/js/devexpress-web-14.1/js/globalize.min.js"></script>
    <!--   <script src="../assets/js/devexpress-web-14.1/js/dx.chartjs.js"></script>-->
    <script src="../assets/js/toastr/toastr.min.js"></script>


    
    <script src="../assets/js/jquery-ui/jquery-ui.js"></script>
    <script src="../assets/js/knob/jquery.knob.min.js"></script>

    <!-- JavaScripts initializations and stuff -->
    <script src="../assets/js/xenon-custom.js"></script>
    
    <script src="../assets/js/d3.min.js"></script>
    <script src="../assets/js/viz-1.0.3.js"></script>
    <script src="../assets/js/visualgo_print.js"></script>
    <script src="../assets/js/graph_library.js"></script>
    <script type="text/javascript">
        // MaxFlow Widget
        // original author: Jonathan Irvin Gunawan, then maintained by Steven Halim
        
        // Maximum Flow Example Constants
        var noOfExamples = 6;
        var INF = 1000000000;
        
        var MaxFlow = function() {
          var gw = new GraphWidget();
        
          var iVL = {};
          var iEL = {};
          var amountVertex = 0;
          var amountEdge = 0;
          var stateList = [];
        
          this.getGraphWidget = function() { return gw; }
        
          fixJSON = function() {
            amountVertex = 0;
            amountEdge = 0;
            for (var key in iVL) ++amountVertex;
            for (var key in iEL) ++amountEdge;
        
            for (var key in iEL) iEL[key]["w"] = +iEL[key]["w"]; // make it intege weight
        
            // for (var key in iEL) {
            //   iEL[key]["type"] = EDGE_TYPE_UDE;
            //   iEL[key]["displayWeight"] = true;
            // }
            // for (var key in iVL)
            //   iVL[key]["text"] = key;
            // for (var key in iEL) {
            //   iVL[iEL[key]["vertexA"]][iEL[key]["vertexB"]] = +key;
            //   iVL[iEL[key]["vertexB"]][iEL[key]["vertexA"]] = +key;
            //   iEL[key]["weight"] = +iEL[key]["weight"];
            // }
          }
        
          takeJSON = function(graph) {
            if (graph == null) return;
            graph = JSON.parse(graph);
            iVL = graph["vl"];
            iEL = graph["el"];
            fixJSON();
          }
        
          statusChecking = function() {
            if (amountVertex == 0) $("#draw-status p").html("图是空的。<div>请画一个<b>带权网络流</b>图</div>");
            else                   $("#draw-status p").html("请画一个连通源点#0和汇点#{lastVertex}（最后的点）的带权网络流图。注意：边的权重代表边的容量".replace("{lastVertex}", amountVertex-1));
            $("#sinkvertex").val(amountVertex-1);
          }
        
          warnChecking = function() {
            var warn = "";
            if (amountVertex >= 10) warn += "屏幕上的点太多，考虑画小一点的图。";
        
            if (warn == "") $("#draw-warn p").html("没有警告");
            else $("#draw-warn p").html(warn);
          }
        
          errorChecking = function() {
            var error = "";
            if (amountVertex == 0) {
              $("#draw-err p").html("图不能为空。");
              return;
            }
            
            var visited = [];
            var stack = [];
            stack.push(0);
            visited[0] = true;
            while (stack.length > 0) {
              var now = stack.pop();
              for (var key2 in iEL) if(iEL[key2]["u"] == now) {
                if (!visited[iEL[key2]["v"]]) {
                  visited[iEL[key2]["v"]] = true;
                  stack.push(+iEL[key2]["v"]);
                }
              }
            }
            if (!visited[amountVertex-1]) 
              error = error + "源点和汇点没有连通。"
            var leftmost = INF, rightmost = -INF;
            for (var key in iVL) {
              leftmost = Math.min(leftmost,iVL[key]["x"]);
              rightmost = Math.max(rightmost,iVL[key]["x"]);
            }
            if (leftmost < iVL[0]["x"])
              error = error + "源点不在最左边。"
            if (rightmost > iVL[amountVertex-1]["x"])
              error = error + "汇点不在最右边。"
        
            if (error == "") $("#draw-err p").html("没有错误");
            else $("#draw-err p").html(error);
          }
        
          var intervalID;
        
          this.startLoop = function() {
            intervalID = setInterval(function() {
              takeJSON(JSONresult);
              warnChecking();
              errorChecking();
              statusChecking();
            }, 100);
          }
        
          this.stopLoop = function() { clearInterval(intervalID); }
          
          this.draw = function() {
            if ($("#draw-err p").html() != "没有错误") return false;
            if ($("#submit").is(':checked'))
              this.submit(JSONresult);
            if ($("#copy").is(':checked'))
              window.prompt("复制到剪贴板：",JSONresult);
            graph = createState(iVL, iEL);
            gw.updateGraph(graph, 500);
            return true;
          }
        
          this.submit = function(graph) {
            $.ajax({
              url: PHP_DOMAIN + "/php/Graph.php?mode=" + MODE_SUBMIT_GRAPH + "&sessionID=" + $.cookie("sessionID"),
              type: "POST",
              data: {canvasWidth: 1000, canvasHeight: 500, graphTopics: 'Max Flow', graphState: graph},
              error: function(xhr, errorType, exception) { //Triggered if an error communicating with server  
                  var errorMessage = exception || xhr.statusText; //If exception null, then default to xhr.statusText  
        
                  alert("提交你的图时有错误" + errorMessage);
              }
            }).done(function(data) {
              console.log(data);
            });
          }
        
          this.importjson = function(text) {
            //var text = $("#samplejson-input").val();
            takeJSON(text);
            statusChecking();
            graph = createState(iVL,iEL);
            gw.updateGraph(graph, 500);
          }
            
          this.initRandom = function(graph) {
            iVL = graph.iVL;
            iEL = graph.iEL;
            amountVertex = iVL.length;
            amountEdge = iEL.length;
            fixJSON();
            statusChecking();
            var newState = createState(iVL, iEL);
        
            gw.updateGraph(newState, 500);
          }
        
          //returns index of edge in iEL that connects vertexA to vertexB, eh this can be put in helper object...
          var findEdgeIndex = function(vertexA, vertexB) {
            for (i in iEL)
              if (iEL[i]["u"] == vertexA && iEL[i]["v"] == vertexB)
                return i;
            return -1;
          }
        
          this.fordfulkerson = function(sourceVertex, sinkVertex) {
            var existAugmentingPath = true;
            var MaxFlow = 0;
            var numberOfAugmentingPaths = 0;
        
            while (existAugmentingPath) {
              numberOfAugmentingPaths++;
              existAugmentingPath = false;
              var edgeYellow = {};
              var edgeRed = {};
              var edgeBlue = {};
              var vertexTraversed = {};
              var vertexHighlighted = {};
              var parent = new Array(amountVertex);
              var visited = new Array(amountVertex);
              for (i in iVL) {
                parent[i] = -1;
                visited[i] = false;
              }
        
              var DFSStack = [];
              DFSStack.push([sourceVertex,INF]);
              while (DFSStack.length > 0) {
                var now = DFSStack.pop(); // last most item
                var nowVertex = now[0];
                var nowCapacity = +now[1];
                if (visited[nowVertex]) continue;
                visited[nowVertex] = true;
                if (nowVertex == sinkVertex) {
                  var path = [];
                  while (nowVertex != sourceVertex) {
                    path.push(nowVertex);
                    nowVertex = parent[nowVertex];
                  }
                  path.push(sourceVertex);
                  var bottleneck = [-1,-1]; //[forward edge,back edge]
        
                  for (var i = path.length-1; i >= 1; --i) {
                    var backEdge = findEdgeIndex(path[i-1],path[i]);
                    var forwardEdge = findEdgeIndex(path[i],path[i-1]);
                    if (bottleneck[0] == -1 || iEL[forwardEdge]["w"] < iEL[bottleneck[0]]["w"]) {
                      if (bottleneck[0] != -1) {
                        delete edgeRed[bottleneck[0]];
                        delete edgeRed[bottleneck[1]];
                        edgeYellow[bottleneck[0]] = true;
                        edgeYellow[bottleneck[1]] = true;
                      }
                      edgeRed[backEdge] = true;
                      edgeRed[forwardEdge] = true;
                      bottleneck = [forwardEdge, backEdge];
                    }
                    else {
                      edgeYellow[backEdge] = true;
                      edgeYellow[forwardEdge] = true;
                    }
                    cs = createState(iVL, iEL, vertexHighlighted, edgeRed, vertexTraversed, edgeYellow);
                    cs["status"] = "当前从{sourceVertex}到{sinkVertex}的最大流为{MaxFlow}。"
                                      .replace("{sourceVertex}", sourceVertex)
                                      .replace("{sinkVertex}", sinkVertex)
                                      .replace("{MaxFlow}", MaxFlow);
                    cs["status"] += "找到一条增广路。瓶颈为{bottleneck}（红色的边）".replace("{bottleneck}", iEL[bottleneck[0]]["w"]);
                    cs["lineNo"] = [3];
                    stateList.push(cs);
                  }
        
                  cs = createState(iVL, iEL, vertexHighlighted, edgeRed, vertexTraversed, edgeYellow, edgeBlue);
                  cs["status"] = "当前从{sourceVertex}到{sinkVertex}的最大流为{MaxFlow}。"
                                    .replace("{sourceVertex}", sourceVertex)
                                    .replace("{sinkVertex}", sinkVertex)
                                    .replace("{MaxFlow}", MaxFlow);
                  cs["status"] += "<br>Got an augmenting path. Bottleneck is {bottleneck} (red edge)<br>".replace("{bottleneck}", nowCapacity);
                  cs["lineNo"] = [3];
                  stateList.push(cs);
        
                  nowVertex = sinkVertex;
                  while (nowVertex != sourceVertex) {            
                    var backEdge = findEdgeIndex(nowVertex,parent[nowVertex]);
                    var forwardEdge = findEdgeIndex(parent[nowVertex],nowVertex);
        
                    iEL[forwardEdge]["w"] -= nowCapacity;
                    iEL[backEdge]["w"] += nowCapacity;
        
                    var bottleneck = false;
        
                    if (edgeRed.hasOwnProperty(backEdge)) bottleneck = true;
        
                    if (bottleneck) {
                      delete edgeRed[forwardEdge];
                      delete edgeRed[backEdge];
                    }
                    else {
                      delete edgeYellow[forwardEdge];
                      delete edgeYellow[backEdge];
                    }
        
                    edgeBlue[forwardEdge] = true;
                    edgeBlue[backEdge] = true;
        
                    cs = createState(iVL, iEL, vertexHighlighted, edgeRed, vertexTraversed, edgeYellow, edgeBlue);
                    cs["status"] = "当前从{sourceVertex}到{sinkVertex}的最大流为{MaxFlow}。"
                                      .replace("{sourceVertex}", sourceVertex)
                                      .replace("{sinkVertex}", sinkVertex)
                                      .replace("{MaxFlow}", MaxFlow);
                    cs["status"] += "瓶颈为{bottleneck}（红色的边）。正在更新从{parent}到{nowVertex}的边（蓝色的边）"
                                      .replace("{bottleneck}", nowCapacity)
                                      .replace("{parent}", parent[nowVertex])
                                      .replace("{nowVertex}", nowVertex);
                    cs["lineNo"] = [4, 5, 6];
        
                    nowVertex = parent[nowVertex];
                    stateList.push(cs);
        
                    delete edgeBlue[forwardEdge];
                    delete edgeBlue[backEdge];
        
                    if (bottleneck) {
                      edgeRed[forwardEdge] = true;
                      edgeRed[backEdge] = true;
                    }
                    else {
                      edgeYellow[forwardEdge] = true;
                      edgeYellow[backEdge] = true;
                    }
        
                  }
                  existAugmentingPath = true;
                  MaxFlow += nowCapacity;
                  cs = createState(iVL, iEL, vertexHighlighted, edgeRed, vertexTraversed, edgeYellow, edgeBlue);
                  cs["status"] = "当前从{sourceVertex}到{sinkVertex}的最大流为{MaxFlow}。"
                                    .replace("{sourceVertex}", sourceVertex)
                                    .replace("{sinkVertex}", sinkVertex)
                                    .replace("{MaxFlow}", MaxFlow);
                  cs["status"] += "最大流增长了{nowCapacity}".replace("{nowCapacity}", nowCapacity);
                  cs["lineNo"] = [7];
                  stateList.push(cs);
                  break;
                }
                var DFStempStack = [];
                for (i in iEL) {
                  var vertexA = iEL[i]["u"];
                  var vertexB = iEL[i]["v"];
                  var capacity = iEL[i]["w"];
                  if (nowVertex == vertexA && !visited[vertexB] && capacity > 0) {
                    parent[vertexB] = vertexA;
                    if (numberOfAugmentingPaths % 2 == 0 && nowVertex == 0) {
                      if (capacity < nowCapacity)
                        DFStempStack.push([vertexB,capacity]);
                      else DFStempStack.push([vertexB,nowCapacity]);
                    }
                    else {
                      if (capacity < nowCapacity)
                        DFSStack.push([vertexB,capacity]);
                      else DFSStack.push([vertexB,nowCapacity]);
                    }
                  }
                }
                while (DFStempStack.length > 0)
                  DFSStack.push(DFStempStack.pop());
              }
            }
        
            cs = createState(iVL, iEL, vertexHighlighted, edgeRed, vertexTraversed, edgeYellow, edgeBlue);
            cs["status"] = "从{sourceVertex}到{sinkVertex}的最大流为{MaxFlow}。<div>没有更多的增广路。</div>"
                              .replace("{sourceVertex}", sourceVertex)
                              .replace("{sinkVertex}", sinkVertex)
                              .replace("{MaxFlow}", MaxFlow);
            cs["lineNo"] = [];
            stateList.push(cs);
            populatePseudocode(1);
        
            return MaxFlow;
          }
        
          this.edmondskarp = function(sourceVertex, sinkVertex) {
            var existAugmentingPath = true;
            var MaxFlow = 0;
        
            while (existAugmentingPath) {
              existAugmentingPath = false;
              var edgeYellow = {};
              var edgeRed = {};
              var edgeBlue = {};
              var vertexTraversed = {};
              var vertexHighlighted = {};
              var parent = new Array(amountVertex);
              var visited = new Array(amountVertex);
              for (i in iVL) {
                parent[i] = -1;
                visited[i] = false;
              }
        
              var BFSQueue = [];
              BFSQueue.push([sourceVertex,INF]);
              visited[sourceVertex] = true;
              while (BFSQueue.length > 0)  {
                var now = BFSQueue.shift(); // pop front item
                var nowVertex = now[0];
                var nowCapacity = +now[1];
                if (nowVertex == sinkVertex) {
                  var path = [];
                  while (nowVertex != sourceVertex) {
                    path.push(nowVertex);
                    nowVertex = parent[nowVertex];
                  }
                  path.push(sourceVertex);
                  var bottleneck = [-1, -1]; //[forward edge,back edge]
        
                  for (var i = path.length-1; i >= 1; i--) {
                    var backEdge = findEdgeIndex(path[i-1],path[i]);
                    var forwardEdge = findEdgeIndex(path[i],path[i-1]);
                    //if capacity < bottleneck
                    if (bottleneck[0] == -1 || iEL[forwardEdge]["w"] < iEL[bottleneck[0]]["w"]) {
                      // update bottleneck
                      if (bottleneck[0] != -1) {
                        delete edgeRed[bottleneck[0]];
                        delete edgeRed[bottleneck[1]];
                        edgeYellow[bottleneck[0]] = true;
                        edgeYellow[bottleneck[1]] = true;
                      }
                      edgeRed[backEdge] = true;
                      edgeRed[forwardEdge] = true;
                      bottleneck = [forwardEdge,backEdge];
                    }
                    else {
                      edgeYellow[backEdge] = true;
                      edgeYellow[forwardEdge] = true;
                    }
                    cs = createState(iVL, iEL, vertexHighlighted, edgeRed, vertexTraversed, edgeYellow);
                     cs["status"] = "当前从{sourceVertex}到{sinkVertex}的最大流为{MaxFlow}。"
                                      .replace("{sourceVertex}", sourceVertex)
                                      .replace("{sinkVertex}", sinkVertex)
                                      .replace("{MaxFlow}", MaxFlow);
                    cs["status"] += "找到一条增广路。瓶颈为{bottleneck}（红色的边）".replace("{bottleneck}", iEL[bottleneck[0]]["w"]);
                    cs["lineNo"] = [3];
                    //stateList.push(cs); // SH7: quick visual bug fix (EK's BFS looks like DFS) by not saving this state in the stateList
                  }
        
                  cs = createState(iVL, iEL, vertexHighlighted, edgeRed, vertexTraversed, edgeYellow);
                  cs["status"] = "当前从{sourceVertex}到{sinkVertex}的最大流为{MaxFlow}。"
                                    .replace("{sourceVertex}", sourceVertex)
                                    .replace("{sinkVertex}", sinkVertex)
                                    .replace("{MaxFlow}", MaxFlow);
                  cs["status"] += "<br>Got an augmenting path. Bottleneck is {bottleneck} (red edge)<br>".replace("{bottleneck}", nowCapacity);
                  cs["lineNo"] = [3];
                  stateList.push(cs);
        
                  nowVertex = sinkVertex;
        
                  while (nowVertex != sourceVertex) {
                    var backEdge = findEdgeIndex(nowVertex,parent[nowVertex]);
                    var forwardEdge = findEdgeIndex(parent[nowVertex],nowVertex);
        
                    iEL[forwardEdge]["w"] -= nowCapacity;
                    iEL[backEdge]["w"] += nowCapacity;
        
                    var bottleneck = false;
        
                    if (edgeRed.hasOwnProperty(backEdge)) bottleneck = true;
        
                    if (bottleneck) {
                      delete edgeRed[forwardEdge];
                      delete edgeRed[backEdge];
                    }
                    else {
                      delete edgeYellow[forwardEdge];
                      delete edgeYellow[backEdge];
                    }
        
                    edgeBlue[forwardEdge] = true;
                    edgeBlue[backEdge] = true;
        
                    cs = createState(iVL, iEL, vertexHighlighted, edgeRed, vertexTraversed, edgeYellow, edgeBlue);
                    cs["status"] = "当前从{sourceVertex}到{sinkVertex}的最大流为{MaxFlow}。"
                                      .replace("{sourceVertex}", sourceVertex)
                                      .replace("{sinkVertex}", sinkVertex)
                                      .replace("{MaxFlow}", MaxFlow);
                    cs["status"] += "瓶颈为{bottleneck}（红色的边）。正在更新从{parent}到{nowVertex}的边（蓝色的边）"
                                      .replace("{bottleneck}", nowCapacity)
                                      .replace("{parent}", parent[nowVertex])
                                      .replace("{nowVertex}", nowVertex);
                    cs["lineNo"] = [4, 5, 6];
        
                    nowVertex = parent[nowVertex];
                    stateList.push(cs);
        
                    delete edgeBlue[forwardEdge];
                    delete edgeBlue[backEdge];
        
                    if (bottleneck) {
                      edgeRed[forwardEdge] = true;
                      edgeRed[backEdge] = true;
                    }
                    else {
                      edgeYellow[forwardEdge] = true;
                      edgeYellow[backEdge] = true;
                    }
                  }
        
                  existAugmentingPath = true;
                  MaxFlow += nowCapacity;
                  cs = createState(iVL, iEL, vertexHighlighted, edgeRed, vertexTraversed, edgeYellow, edgeBlue);
                  cs["status"] = "当前从{sourceVertex}到{sinkVertex}的最大流为{MaxFlow}。"
                                    .replace("{sourceVertex}", sourceVertex)
                                    .replace("{sinkVertex}", sinkVertex)
                                    .replace("{MaxFlow}", MaxFlow);
                  cs["status"] += "最大流增长了{nowCapacity}".replace("{nowCapacity}", nowCapacity);
                  cs["lineNo"] = [7];
                  stateList.push(cs);
                  break;
                }
                for (i in iEL) {
                  var vertexA = iEL[i]["u"];
                  var vertexB = iEL[i]["v"];
                  var capacity = iEL[i]["w"];
                  if (nowVertex == vertexA && !visited[vertexB] && capacity > 0) {
                    visited[vertexB] = true;
                    parent[vertexB] = vertexA;
                    if (capacity < nowCapacity)
                      BFSQueue.push([vertexB,capacity]);
                    else BFSQueue.push([vertexB,nowCapacity]);
                  }
                }
              }
            }
        
            cs = createState(iVL, iEL, vertexHighlighted, edgeRed, vertexTraversed, edgeYellow, edgeBlue);
            cs["status"] = "从{sourceVertex}到{sinkVertex}的最大流为{MaxFlow}。<div>没有更多的增广路。</div>"
                              .replace("{sourceVertex}", sourceVertex)
                              .replace("{sinkVertex}", sinkVertex)
                              .replace("{MaxFlow}", MaxFlow);
            cs["lineNo"] = [];
            stateList.push(cs);
            populatePseudocode(0);
        
            return MaxFlow;
          }
        
          this.dinic = function(sourceVertex, sinkVertex) {
            var existBlockingFlow = true;
            var MaxFlow = 0;
        
            while (existBlockingFlow) {
              existBlockingFlow = false;
              var edgeBlue = {};
              var vertexTraversed = {};
              var vertexHighlighted = {};
              var visited = new Array(amountVertex);
              var distance = new Array(amountVertex);
              for (i in iVL) {
                visited[i] = false;
                distance[i] = INF;
              }
        
              var BFSQueue = [];
              BFSQueue.push(sourceVertex);
              distance[sourceVertex] = 0;
              while (BFSQueue.length > 0) {
                var nowVertex = BFSQueue.shift();
                for (i in iEL) {
                  var vertexA = iEL[i]["u"];
                  var vertexB = iEL[i]["v"];
                  var capacity = iEL[i]["w"];
                  if (nowVertex == vertexA && distance[vertexB] == INF && capacity > 0) {
                    distance[vertexB] = distance[vertexA] + 1;
                    BFSQueue.push(vertexB);
                  }
                }
              }
              for (i in iEL) {
                var vertexA = iEL[i]["u"];
                var vertexB = iEL[i]["v"];
                var capacity = iEL[i]["w"];
                if (capacity > 0 && distance[vertexB] == distance[vertexA]+1 && distance[vertexB] <= distance[sinkVertex]) {
                  edgeBlue[i] = true;
                  edgeBlue[findEdgeIndex(vertexB,vertexA)] = true;
                }
              }
        
              if (distance[sinkVertex] == INF) break;
              
              cs = createState(iVL, iEL, vertexHighlighted, edgeRed, vertexTraversed, edgeYellow, edgeBlue);
              cs["status"] = "从{sourceVertex}到{sinkVertex}的最大流为{MaxFlow}。<div>找到了层级图（蓝色的边）。汇点在第{distance}层。</div>"
                              .replace("{sourceVertex}", sourceVertex)
                              .replace("{sinkVertex}", sinkVertex)
                              .replace("{MaxFlow}", MaxFlow)
                              .replace("{distance}", distance[sinkVertex]);
              cs["lineNo"] = [3];
              stateList.push(cs);
        
              var edgeBlueTemp = edgeBlue;
              var existAugmentingPath = true;
              while (existAugmentingPath) {
                existAugmentingPath = false;
                edgeBlue = edgeBlueTemp;
                var edgeYellow = {};
                var edgeRed = {};
                var parent = new Array(amountVertex);
        
                var DFSStack = [];
                DFSStack.push([sourceVertex,INF]);
                while (DFSStack.length > 0) {
                  var now = DFSStack.pop(); //last most item
                  var nowVertex = now[0];
                  var nowCapacity = +now[1];
                  if (nowVertex == sinkVertex) {
                    while (nowVertex != sourceVertex) { 
                      var backEdge = findEdgeIndex(nowVertex,parent[nowVertex]);
                      var forwardEdge = findEdgeIndex(parent[nowVertex],nowVertex);
        
                      delete edgeBlue[backEdge]; 
                      delete edgeBlue[forwardEdge];
        
                      if (iEL[forwardEdge]["w"] != nowCapacity) {
                        edgeYellow[backEdge] = true;
                        edgeYellow[forwardEdge] = true;
                      }
                      else {
                        edgeRed[backEdge] = true;
                        edgeRed[forwardEdge] = true;
                      }
        
                      nowVertex = parent[nowVertex];
                    }
                    cs = createState(iVL, iEL, vertexHighlighted, edgeRed, vertexTraversed, edgeYellow, edgeBlue);
                    cs["status"] = "当前从{sourceVertex}到{sinkVertex}的最大流为{MaxFlow}。"
                                    .replace("{sourceVertex}", sourceVertex)
                                    .replace("{sinkVertex}", sinkVertex)
                                    .replace("{MaxFlow}", MaxFlow);
                    cs["status"] += "找到一个阻塞流。瓶颈为{bottleneck}（红色的边）".replace("{bottleneck}", nowCapacity);
                    cs["lineNo"] = [4];
                    stateList.push(cs);
        
                    nowVertex = sinkVertex;
                    while (nowVertex != sourceVertex) {            
                      var backEdge = findEdgeIndex(nowVertex, parent[nowVertex]);
                      var forwardEdge = findEdgeIndex(parent[nowVertex], nowVertex);
        
                      iEL[forwardEdge]["w"] -= nowCapacity;
                      iEL[backEdge]["w"] += nowCapacity;
        
                      var bottleneck = false;
        
                      if (edgeRed.hasOwnProperty(backEdge)) bottleneck = true;
        
                      cs = createState(iVL, iEL, vertexHighlighted, edgeRed, vertexTraversed, edgeYellow, edgeBlue);
                      cs["status"] = "当前从{sourceVertex}到{sinkVertex}的最大流为{MaxFlow}。"
                                    .replace("{sourceVertex}", sourceVertex)
                                    .replace("{sinkVertex}", sinkVertex)
                                    .replace("{MaxFlow}", MaxFlow);
                      cs["status"] += "瓶颈为{bottleneck}（红色的边）。正在更新从{parent}到{nowVertex}的边（蓝色的边）"
                                      .replace("{bottleneck}", nowCapacity)
                                      .replace("{parent}", parent[nowVertex])
                                      .replace("{nowVertex}", nowVertex);
                      cs["lineNo"] = [5];
        
                      nowVertex = parent[nowVertex];
                      stateList.push(cs);
                    }
        
                    existAugmentingPath = true;
                    existBlockingFlow = true;
                    MaxFlow += nowCapacity;
                    cs = createState(iVL, iEL, vertexHighlighted, edgeRed, vertexTraversed, edgeYellow, edgeBlue);
                    cs["status"] = "当前从{sourceVertex}到{sinkVertex}的最大流为{MaxFlow}。"
                                    .replace("{sourceVertex}", sourceVertex)
                                    .replace("{sinkVertex}", sinkVertex)
                                    .replace("{MaxFlow}", MaxFlow);
                    cs["status"] += "最大流增长了{nowCapacity}".replace("{nowCapacity}", nowCapacity);
                    cs["lineNo"] = [6];
                    stateList.push(cs);
                    break;
                  }
                  for (i in iEL) {
                    var vertexA = iEL[i]["u"];
                    var vertexB = iEL[i]["v"];
                    var capacity = iEL[i]["w"];
                    if (nowVertex == vertexA && capacity > 0 && distance[vertexA]+1 == distance[vertexB]) {
                      parent[vertexB] = vertexA;
                      if (capacity < nowCapacity)
                        DFSStack.push([vertexB,capacity]);
                      else DFSStack.push([vertexB,nowCapacity]);
                    }
                  }
                }
              }
            }
        
            cs = createState(iVL, iEL, vertexHighlighted, edgeRed, vertexTraversed, edgeYellow, edgeBlue);
            cs["status"] = "<div>从{sourceVertex}到{sinkVertex}的最大流为{MaxFlow}。<br></div><div>没有更多从源点到汇点的流</div>"
                            .replace("{sourceVertex}", sourceVertex)
                            .replace("{sinkVertex}", sinkVertex)
                            .replace("{MaxFlow}", MaxFlow);
            cs["lineNo"] = [];
            stateList.push(cs);
            populatePseudocode(2);
        
            return MaxFlow;
          }
        
          this.countmincut = function(sourceVertex, sinkVertex, originalCap, mf) {
            var edgeRed = {};
            var vertexTraversed = {};
            var vertexHighlighted = {};
            var visited = new Array(amountVertex);
            var distance = new Array(amountVertex);
            for (i in iVL) {
              visited[i] = false;
              distance[i] = INF;
            }
        
            var BFSQueue = [];
            BFSQueue.push(sourceVertex);
            distance[sourceVertex] = 0;
            while (BFSQueue.length > 0) {
              var nowVertex = BFSQueue.shift();
              vertexTraversed[nowVertex] = true;
              if (nowVertex != sourceVertex)
                iVL[nowVertex]["extratext"] = "S";
              for (i in iEL) {
                var vertexA = iEL[i]["u"];
                var vertexB = iEL[i]["v"];
                var capacity = iEL[i]["w"];
                if (nowVertex == vertexA && distance[vertexB] == INF && capacity > 0) {
                  distance[vertexB] = distance[vertexA] + 1;
                  BFSQueue.push(vertexB);
                }
              }
            }
        
            for (i in iVL)
              if (!vertexTraversed[i]) { // in T-component
                vertexHighlighted[i] = true;
                if (i != sinkVertex)
                  iVL[i]["extratext"] = "T";
              }
        
            for (j in iEL) {
              var vertexA = iEL[j]["u"];
              var vertexB = iEL[j]["v"];
              var capacity = iEL[j]["w"];
              if (vertexTraversed[vertexA] && vertexHighlighted[vertexB]) { // highlight edges that crosses S-component to T-component
                edgeRed[j] = true;
                edgeRed[findEdgeIndex(vertexB,vertexA)] = true;
              }
              // this part still confusing, take more time to think... use the uni-directional flow strategy, if both f(u, v) > 0 and f(v, u) > 0, they will cancel out eah other
              // if (originalCap[j] != 0) // not a new back flow
              //   iEL[j]["w"] = (originalCap[j]-iEL[j]["w"]) + "/" + originalCap[j]; // show the actual flow on this edge w.r.t original capacity of this edge
              // else
              //   iEL[j]["w"] = "N/A";
            }
        
            cs = createState(iVL, iEL, vertexHighlighted, edgeRed, vertexTraversed, {}, {});
            cs["status"] = "从{sourceVertex}到{sinkVertex}的最大流（最小割）是{mf}。<div>穿过S-T割的边被高亮显示。</div>"
                            .replace("{sourceVertex}", sourceVertex)
                            .replace("{sinkVertex}", sinkVertex)
                            .replace("{mf}", mf);
            cs["lineNo"] = [];
            stateList.push(cs);
          }
        
          this.countmaxflow = function(algorithm, sourceVertex, sinkVertex) {
            stateList = [];
        
            // error checks
            if (amountVertex == 0) { // no graph
              $('#countmaxflow-err').html("没有图来运行此算法。请先选一个示例图。");
              return false;
            }
        
            if (sourceVertex >= amountVertex || sourceVertex < 0) { // source vertex not in range
              $('#countmaxflow-err').html("源点在图中不存在");
              return false;
            }
        
            if (sinkVertex >= amountVertex || sinkVertex < 0) { // sink vertex not in range
              $('#countmaxflow-err').html("汇点在图中不存在");
              return false;
            }
        
            if (sourceVertex == sinkVertex) {
              $('#countmaxflow-err').html("源点和汇点是同一点");
              return false;
            }
        
            for (i in iVL) {
              if (i >= amountVertex) delete iVL[i];
              iVL[i]["extratext"] = "";
            }
        
            iVL[sourceVertex]["extratext"] = "source";
            iVL[sinkVertex]["extratext"] = "sink";
            var cs = createState(iVL, iEL);
            cs["status"] = "当前从{sourceVertex}到{sinkVertex}的最大流为{MaxFlow}。"
                            .replace("{sourceVertex}", sourceVertex)
                            .replace("{sinkVertex}", sinkVertex)
                            .replace("{MaxFlow}", 0);
            cs["status"] += "原始的网络流图。";
            cs["lineNo"] = [1];
            stateList.push(cs);
        
            //creating residual graph (backedges for every edge)
            for (i in iEL) {
              var backEdge = new Object();
              backEdge["u"] = iEL[i]["v"];
              backEdge["v"] = iEL[i]["u"];
              backEdge["w"] = 0;
              // if backEdge is not on the iEL yet
              if (findEdgeIndex(backEdge["u"], backEdge["v"]) == -1) { // insert backEdge to iEL
                iEL[amountEdge] = (backEdge);
                amountEdge++;
              }
            }
        
            var originalCap = {};
            for (i in iEL) {
              if (i >= amountEdge) delete iEL[i];
              originalCap[i] = +iEL[i]["w"];
            }
        
            var cs = createState(iVL, iEL);
            cs["status"] = "当前从{sourceVertex}到{sinkVertex}的最大流为{MaxFlow}。"
                            .replace("{sourceVertex}", sourceVertex)
                            .replace("{sinkVertex}", sinkVertex)
                            .replace("{MaxFlow}", 0);
            cs["status"] += "准备残留网络中。";
            cs["lineNo"] = [1];
            stateList.push(cs);
        
            // run the maxflow algorithm
            var mf = 0;
                 if (algorithm == "fordfulkerson") mf = this.fordfulkerson(sourceVertex,sinkVertex);
            else if (algorithm == "edmondskarp")   mf = this.edmondskarp(sourceVertex,sinkVertex);
            else if (algorithm == "dinic")         mf = this.dinic(sourceVertex,sinkVertex);
        
            this.countmincut(sourceVertex, sinkVertex, originalCap, mf);
        
            gw.startAnimation(stateList);
            return true;
          }
        
          this.rookattack = function() {
            var numOfRows = parseInt($('#rows').val());
            var numOfColumns = parseInt($('#columns').val());
            var blocked = new Array(numOfRows);
        
            for (var i = 0; i < numOfRows; i++) {
              blocked[i] = new Array(numOfColumns);
              for (var j = 0; j < numOfColumns; j++)
                blocked[i][j] = false;
            }
        
            if (numOfRows < 1 || numOfColumns < 1 || numOfRows > 6 || numOfColumns > 6) { // no graph
              $('#modeling-err').html("无效的大小。行和列的大小必须在1到6之间（包含）。");
              return false;
            }
        
            this.changeState = function(rowIndex,columnIndex) {
              var temp = '#cell' + rowIndex + columnIndex;
              if (blocked[rowIndex][columnIndex]) {
                $(temp).attr("bgcolor","white");
                blocked[rowIndex][columnIndex] = false;
              }
              else {
                $(temp).attr("bgcolor","black");
                blocked[rowIndex][columnIndex] = true;
              }
            }
        
            this.createBipartiteGraph = function() {
              iVL = {};
              iEL = {};
              vertexHighlighted = {};
              edgeRed = {};
              stateList = [];
              var cs;
              amountEdge = 0;
              amountVertex = 2 + numOfRows + numOfColumns;
        
              iVL[0] = {
                "x": 25,
                "y": 175,
              }
        
              iVL[amountVertex-1] = {
                "x": 625,
                "y": 175,
              }
        
              vertexHighlighted[0] = vertexHighlighted[amountVertex-1] = true;
              cs = createState(iVL, iEL,vertexHighlighted);
              cs["status"] = "创建源点和汇点";
              cs["lineNo"] = [1];
              stateList.push(cs);
              delete vertexHighlighted[0]; delete vertexHighlighted[amountVertex-1];
        
              for (var i = 1; i <= numOfRows; i++) {
                iVL[i] = {
                  "x": 225,
                  "y": (175 + (i - (numOfRows+1)/2) * (numOfRows == 1 ? 0 : 300/(numOfRows-1))),
                  "text": "R"+i
                }
                iEL[amountEdge] = {
                  "u": 0,
                  "v": i,
                  "w": 1
                }
                amountEdge++;
                vertexHighlighted[i] = true;
              }
        
              cs = createState(iVL, iEL,vertexHighlighted);
              cs["status"] = "Create a vertex for each rows<br>and connect the source vertex to each vertex with capacity 1</br>";
              cs["lineNo"] = [2];
              stateList.push(cs);
              for (var i = 1; i <= numOfRows; ++i)
                delete vertexHighlighted[i];
        
              for (var i = 1; i <= numOfColumns; ++i) {
                iVL[i+numOfRows] = {
                  "x": 425,
                  "y": (175 + (i-(numOfColumns+1)/2) * (numOfColumns == 1 ? 0 : 300/(numOfColumns-1))),
                  "text": "C"+i
                }
                iEL[amountEdge] = {
                  "u": i+numOfRows,
                  "v": amountVertex-1,
                  "w": 1
                }
                amountEdge++;
                vertexHighlighted[i+numOfRows] = true;
              }
              cs = createState(iVL, iEL,vertexHighlighted);
              cs["status"] = "Create a vertex for each columns<br>and connect each vertex to the sink vertex with capacity 1</br>";
              cs["lineNo"] = [3];
              stateList.push(cs);
              for (var i = 1; i <= numOfColumns; i++)
                delete vertexHighlighted[i+numOfRows];
        
              for (var i = 0; i < numOfRows; i++) {
                for (var j = 0; j < numOfColumns; j++) {
                  var existEdge = 1-blocked[i][j];
                  if (existEdge == 1) {
                    iEL[amountEdge] = {
                      "u": i+1,
                      "v": j+1+numOfRows,
                      "w": 9
                    }
                    amountEdge++;
                    edgeRed[amountEdge-1] = true;
                    cs = createState(iVL, iEL,vertexHighlighted, edgeRed);
                    cs["status"] = "Adding edge from R{row} to C{column}."
                                    .replace("{row}", i+1)
                                    .replace("{column}", j+1);
                    cs["lineNo"] = [4,5];
                    stateList.push(cs);
                    delete edgeRed[amountEdge-1];
                  }
                }
              }
        
              amountVertex = 0;
              amountEdge = 0;
              for (var i in iVL) amountVertex++;
              for (var i in iEL) amountEdge++;
        
              $('#sourcevertex').val(0);
              $('#sinkvertex').val(amountVertex-1);
        
              cs = createState(iVL, iEL);
              cs["status"] = "Run any maximum flow algorithm from 0 to {lastVertex}<br>to get the value of the maximum rooks that can be placed</br>".replace("{lastVertex}", amountVertex-1);
              cs["lineNo"] = [6];
              stateList.push(cs);
              gw.startAnimation(stateList);
              return true;
            }
        
            this.inputFinished = function() {
              $('.overlays').hide("slow");
              $('#dark-overlay').hide("slow");
              $('#rookattack-board').hide("slow");
              mfw.createBipartiteGraph();
              $('#current-action').show();
              $('#current-action p').html("Modeling()");
              $('#progress-bar').slider( "option", "max", gw.getTotalIteration()-1);
              triggerRightPanels();
              populatePseudocode(3);
              isPlaying = true;
              return true;
            }
        
            this.cancel = function() {
              $('.overlays').hide("slow");
              $('#dark-overlay').hide("slow");
              $('#rookattack-board').hide("slow");
              $('#progress-bar').slider( "option", "max", gw.getTotalIteration()-1);
              return true;
            }
        
            this.inputRandomized = function() {
              for (var i = 0; i < numOfRows; i++)
                for (var j = 0; j < numOfColumns; j++)
                  if (Math.random() < 0.5) this.changeState(i,j);
            }
        
            $('#dark-overlay').show("slow");
            var toWrite = '<html>\n';
            toWrite += "<p>Click on any cell to toggle between black/white cell</p>\n";
            toWrite += "<p>Rooks can&#39;t be placed in black cells</p>\n";
            toWrite += '<table border="1" id="board">'
            for (var j = 0; j < numOfColumns; j++)
              toWrite += '<col width="50">';
            for (var i = 0; i < numOfRows; i++) {
              toWrite += '<tr>';
              for (var j = 0; j < numOfColumns; j++)
                toWrite += '<td height="50" bgcolor="white" id="cell' + i + j + '" onclick=mfw.changeState('+i+','+j+')></td>';
              toWrite += '</tr>';
            }
        
            toWrite += '</table>\n';
            toWrite += '<div class="modeling-actions">';
            toWrite += '<p onclick=mfw.inputRandomized()>Randomized</p>';
            toWrite += '<p onclick=mfw.inputFinished()>Done</p>';
            toWrite += '<p onclick=mfw.cancel()>Cancel</p>';
            toWrite += '</div>\n'
            toWrite += '</html>\n';
            $('#rookattack-board').html(toWrite);
            $('#rookattack-board').show("slow");
          }
        
          // this.baseball = function() {
          //   var numOfTeams = parseInt($('#teams').val());
          //   var numOfGames = new Array(numOfTeams);
          //   var initialPoints = new Array(numOfTeams);
          
          //   for (var i = 0; i < numOfTeams; ++i)
          //     numOfGames[i] = new Array(numOfTeams);
        
          //   if (numOfTeams < 1 || numOfTeams > 6) { // no graph
          //     $('#modeling-err').html("Invalid number of teams. Number of teams must be between 1 and 6 inclusive.");
          //     return false;
          //   }
        
          //   setInterval(function()
          //   {
          //     for (var i = 0; i < numOfTeams; ++i)
          //     {
          //       numOfGames[i][i] = 0;
          //       $("#game" + i + i).val(0);
          //       for (var j = 0; j < i; ++j)
          //       {
          //         $("#game" + i + j).val($("#game" + j + i).val());
          //       }
          //     }
          //   },100);
        
          //   this.inputRandomized = function()
          //   {
          //     for (var i = 0; i < numOfTeams; ++i)
          //     {
          //       initialPoints[i] = Math.floor(Math.random() * 10); //0 - 9
          //       $("#point" + i).val(initialPoints[i]);
          //       for (var j = 0; j < numOfTeams; ++j)
          //       {
          //         numOfGames[i][j] = Math.floor(Math.random() * 10); //0 - 9
          //         $("#game" + i + j).val(numOfGames[i][j]);
          //       }
          //     }
          //   }
        
          //   this.createGraph = function(checkTeamIndex)
          //   {
          //     iVL = {};
          //     iEL = {};
          //     vertexHighlighted = {};
          //     edgeRed = {};
          //     stateList = [];
          //     var cs;
          //     var numOfMatches = ((numOfTeams - 1) * (numOfTeams - 2)) / 2;
          //     var totalMaxFlow = 0;
          //     amountEdge = 0;
          //     amountVertex = 2 + numOfMatches + (numOfTeams - 1);
          //     var totalNumberOfGames = new Array(numOfTeams);
          //     var vertexIndex = new Array(numOfTeams);
          //     for (var i = 0; i < numOfTeams; ++i)
          //     {
          //       totalNumberOfGames[i] = 0;
          //       vertexIndex[i] = new Array(numOfTeams);
          //       initialPoints[i] = (+$("#point" + i).val());
          //       for (var j = 0; j < numOfTeams; ++j)
          //       {
          //         numOfGames[i][j] = +($("#game" + i + j).val());
          //         totalNumberOfGames[i] += (numOfGames[i][j]);
          //         console.log(i + " " + j + " " + numOfGames[i][j]);
          //       }
          //     }
        
          //     cs = createState(iVL, iEL,vertexHighlighted);
          //     cs["status"] = 'Assume Team ' + checkTeamIndex + ' wins all remaining games';
          //     cs["status"] += '<br>Team ' + checkTeamIndex + ' will win ' + initialPoints[checkTeamIndex] + ' + ' + totalNumberOfGames[checkTeamIndex];
          //     cs["status"] += ' = ' + (initialPoints[checkTeamIndex] + totalNumberOfGames[checkTeamIndex]) + ' games</br>';
          //     cs["lineNo"] = [1];
          //     stateList.push(cs);
        
          //     for (var i = 0; i < numOfTeams; ++i) if (i != checkTeamIndex)
          //     {
          //       cs = createState(iVL, iEL,vertexHighlighted);
          //       cs["status"] = 'Assume T' + i + ' loses all remaining games. ';
          //       cs["status"] += 'T' + i + ' will win ' + initialPoints[i] + ' games';
          //       if (initialPoints[i] <= initialPoints[checkTeamIndex] + totalNumberOfGames[checkTeamIndex])
          //       {
          //         cs["status"] += '<br>Because ' + initialPoints[i] + '<=' + (initialPoints[checkTeamIndex] + totalNumberOfGames[checkTeamIndex]) + ', team ' + checkTeamIndex + ' can still win the league</br>';
          //         cs["lineNo"] = [1];
          //         stateList.push(cs);     
          //       } else
          //       {
          //         cs["status"] += '<br>Because ' + initialPoints[i] + '>' + (initialPoints[checkTeamIndex] + totalNumberOfGames[checkTeamIndex]) + ', team ' + checkTeamIndex + ' is obviously eliminated</br>';
          //         cs["lineNo"] = [1];
          //         stateList.push(cs);
          //         gw.startAnimation(stateList);
          //         return true;
          //       }   
          //     }
        
        
          //     iVL[0] = {"cx": 25, "cy": 175, "text": 0}
        
          //     iVL[amountVertex - 1] = { "cx": 625, "cy": 175, "text": amountVertex - 1 }
        
          //     vertexHighlighted[0] = vertexHighlighted[amountVertex-1] = true;
          //     cs = createState(iVL, iEL,vertexHighlighted);
          //     cs["status"] = 'Create source and sink vertex';
          //     cs["lineNo"] = [];
          //     stateList.push(cs);
          //     delete vertexHighlighted[0]; delete vertexHighlighted[amountVertex-1];
        
          //     amountVertex = 1;
        
        
          //     //create left set of vertices
          //     for (var i = 0; i < numOfTeams; ++i) if(i != checkTeamIndex)
          //     {
          //       for (var j = i + 1; j < numOfTeams; ++j) if(j != checkTeamIndex)
          //       {
          //         totalMaxFlow += numOfGames[i][j];
          //         iVL[amountVertex] = 
          //         {
          //           "cx": 225,
          //           "cy": (175 + (amountVertex - (numOfMatches + 1) / 2) * (numOfMatches == 1 ? 0 : 300 / (numOfMatches - 1))),
          //           "text": i + "v" + j
          //         }
          //         iEL[amountEdge] = 
          //         {
          //           "vertexA": 0,
          //           "vertexB": amountVertex,
          //           "weight": numOfGames[i][j]
          //         }
          //         vertexHighlighted[amountVertex] = true;
          //         edgeRed[amountEdge] = true;
          //         cs = createState(iVL, iEL,vertexHighlighted, edgeRed);
          //         cs["status"] = 'Create a node for a match between T' + i + ' and T' + j + '. There are ' + numOfGames[i][j] + ' matches remaining';
          //         cs["status"] += '. Connect source vertex to that node with capacity ' + numOfGames[i][j];
          //         cs["lineNo"] = [2,3];
          //         stateList.push(cs);
          //         delete vertexHighlighted[amountVertex];
          //         delete edgeRed[amountEdge];
        
          //         vertexIndex[i][j] = amountVertex;
          //         ++amountVertex;
          //         ++amountEdge;
          //       }
          //     }
        
              
        
          //     //create right set of vertices
          //     for (var i = 0; i < numOfTeams; ++i) if (i != checkTeamIndex)
          //     {
          //       iVL[amountVertex] = 
          //       {
          //         "cx": 425,
          //         "cy": (175 + ((i+(i<checkTeamIndex?1:0)) - (numOfTeams) / 2) * (numOfTeams == 2 ? 0 : 300 / (numOfTeams - 2))),
          //         "text": "T" + i
          //       }
          //       var weight = (+initialPoints[checkTeamIndex]) + (+totalNumberOfGames[checkTeamIndex]) - (+initialPoints[i]);
          //       iEL[amountEdge] = 
          //       {
          //         "vertexA": amountVertex,
          //         "vertexB": 1 + numOfMatches + (numOfTeams - 1),
          //         "weight": weight
          //       }
          //       vertexHighlighted[amountVertex] = true;
          //       edgeRed[amountEdge] = true;
          //       cs = createState(iVL, iEL,vertexHighlighted, edgeRed);
          //       cs["status"] = 'Create a node for a Team ' + i + '. Team ' + i + ' may win ';
          //       cs["status"] += (initialPoints[checkTeamIndex] + totalNumberOfGames[checkTeamIndex]) + '-' + initialPoints[i] + ' = ' + weight + ' matches more';
          //       cs["status"] += '. Connect that node to sink vertex with capacity ' + weight;
          //       cs["lineNo"] = [4,5];
          //       stateList.push(cs);
          //       delete vertexHighlighted[amountVertex];
          //       delete edgeRed[amountEdge];
        
          //       ++amountVertex;
          //       ++amountEdge;
          //     }
        
        
        
          //     //create middle edges
          //     for (var i = 0; i < numOfTeams; ++i) if (i != checkTeamIndex)
          //     {
          //       for (var j = i + 1; j < numOfTeams; ++j) if (j != checkTeamIndex)
          //       {
          //         iEL[amountEdge] = 
          //         {
          //           "vertexA": vertexIndex[i][j],
          //           "vertexB": amountVertex - numOfTeams + i + (i < checkTeamIndex ? 1 : 0),
          //           "weight": 9
          //         }
          //         edgeRed[amountEdge] = true;
          //         ++amountEdge;
        
          //         iEL[amountEdge] = 
          //         {
          //           "vertexA": vertexIndex[i][j],
          //           "vertexB": amountVertex - numOfTeams + j + (j < checkTeamIndex ? 1 : 0),
          //           "weight": 9
          //         }
          //         edgeRed[amountEdge] = true;
          //         ++amountEdge;
        
          //         cs = createState(iVL, iEL,vertexHighlighted, edgeRed);
          //         cs["status"] = 'Adding edge from R' + i + ' to C' + j + ' with capacity INF';
          //         cs["lineNo"] = [6];
          //         //cs["status"] += '<br>Adding edge from R' + i + ' to C' + j + '</br>';
          //         stateList.push(cs);
          //         delete edgeRed[amountEdge-1];
          //         delete edgeRed[amountEdge-2];
          //       }
          //     }
        
          //     amountVertex = 0;
          //     amountEdge = 0;
          //     for (var i in iVL) ++amountVertex;
          //     for (var i in iEL) ++amountEdge;
        
          //     $('#sourcevertex').val(0);
          //     $('#sinkvertex').val(amountVertex-1);
        
          //     cs = createState(iVL, iEL);
          //     cs["status"] = 'Run any maximum flow algorithm from 0 to ' + (amountVertex - 1);
          //     cs["status"] += '. Iff all source edges are saturated (maxflow = ' + totalMaxFlow + '), '
          //     cs["status"] += 'then Team ' + checkTeamIndex + ' is not eliminated';
          //     cs["lineNo"] = [7];
          //     stateList.push(cs);
          //     gw.startAnimation(stateList);
          //     return true;
          //   }
        
          //   this.inputFinished = function(checkTeamIndex)
          //   {
          //     $('.overlays').hide("slow");
          //     $('#dark-overlay').hide("slow");
          //     $('#baseball-board').hide("slow");
          //     mfw.createGraph(checkTeamIndex);
          //     $('#current-action').show();
          //     $('#current-action p').html("Modeling()");
          //     $('#progress-bar').slider( "option", "max", gw.getTotalIteration()-1);
          //     triggerRightPanels();
          //     populatePseudocode(4);
          //     isPlaying = true;
          //     return true;
          //   }
        
          //   this.cancel = function()
          //   {
          //     $('.overlays').hide("slow");
          //     $('#dark-overlay').hide("slow");
          //     $('#rookattack-board').hide("slow");
          //     $('#progress-bar').slider( "option", "max", gw.getTotalIteration()-1);
          //     return true;
          //   }
        
          //   $('#dark-overlay').show("slow");
          //   var toWrite = '<html>\n';
          //   toWrite += '<p>Fill in the table below.\n';
          //   toWrite += ' Don\'t modify the black cells, they will be updated automatically</p>\n';
          //   toWrite += '<p>Click on any team to check whether the team is eliminated or not</p>\n';
          //   toWrite += '<table border="1" id="board">\n';
          //   for (var j = 0; j < numOfTeams + 2; ++j)
          //   {
          //     toWrite += '<col width="50">';
          //   }
        
          //   toWrite += '<tr>';
          //   toWrite += '<td rowspan="2">Team Index</td><td rowspan="2">Initial Points</td>';
          //   toWrite += '<td colspan="5" align="center">Remaining Games</td>';
          //   toWrite += '</tr>';
          //   toWrite += '<tr>';
          //   for (var i = 0; i < numOfTeams; ++i)
          //   {
          //     toWrite += '<td>Team ' + i + '</td>';
          //   }
          //   toWrite += '</tr>';
        
          //   for (var i = 0; i < numOfTeams; ++i)
          //   {
          //     toWrite += '<tr>';
          //     toWrite += '<td><div class="modeling-actions">';
          //     toWrite += '<p onclick=mfw.inputFinished('+i+')>Team ' + i + '</p>';
          //     toWrite += '</div></td>';
          //     toWrite += '<td height="50" bgcolor="white"><input id="point' + i + '" value=0 /></td>';
          //     for (var j = 0; j < numOfTeams; ++j) 
          //     {
          //       if (j > i)
          //       {
          //         toWrite += '<td height="50" bgcolor="white"><input id="game' + i + j + '" value=0 /></td>';
          //       }
          //       else 
          //       {
          //         toWrite += '<td height="50" bgcolor="black"><input style="background-color:black;color:white;" id="game' + i + j + '" value=0 /></td>';
          //       }
          //     }
          //     toWrite += '</tr>';
          //   }
        
          //   toWrite += '</table>\n';
          //   toWrite += '<div class="modeling-actions">';
          //   toWrite += '<p onclick=mfw.inputRandomized()>Randomized</p>';
          //   toWrite += '<p onclick=mfw.cancel()>Cancel</p>';
          //   toWrite += '</div>';
          //   toWrite += '</html>\n';
          //   $('#baseball-board').html(toWrite);
          //   $('#baseball-board').show("slow");
          // }
        
          this.modeling = function(modelingType) {
            iVL = {};
            iEL = {};
            if (modelingType == "rookattack") this.rookattack();
            if (modelingType == "baseball") this.baseball();
            return true;
          }
        
          this.examples = function(id) {
            iVL = getExampleGraph(id, VL);
            iEL = getExampleGraph(id, EL);
            amountVertex = 0;
            amountEdge = 0;
            for (var key in iVL) amountVertex++;
            for (var key in iEL) amountEdge++;
        
            var newState = createState(iVL, iEL);
            gw.updateGraph(newState, 500);
            $('#sourcevertex').val(0);
            $('#sinkvertex').val(amountVertex-1);
            return true;
          }
        
          this.completelyRandom = function() {
            var templateNo = Math.floor(Math.random()*noOfExamples); //0-4
            iVL = $.extend(true, {}, TEMPLATES[templateNo][0]);
            iEL = $.extend(true, {}, TEMPLATES[templateNo][1]);
            amountVertex = TEMPLATES[templateNo][2];
            amountEdge = TEMPLATES[templateNo][3];
        
            //change edge weights
            var keys = Object.keys(iEL);
            var nVertices = Object.keys(iVL).length/2;
            var nEdges = keys.length/2;
            for(var i=0; i<nEdges; i++) {
              //var newWeight = Math.floor(Math.random()*100)-50; //-50-49
              var newWeight = Math.floor(Math.random()*10); //0 - 9
              iEL[keys[i]]["w"] = newWeight;
            }
        
            var newState = createState(iVL, iEL);
            gw.updateGraph(newState, 500);
            return true;
          }
        
          this.bipartiteRandom = function(randomType) { 
            // 0: random
            // 1: left 1
            // 2: right 1
            // 3: all 1
            amountVertex = Math.floor(Math.random()*9) + 4; // 4 to 12
            var numL = Math.floor(Math.random()*(amountVertex-3)) + 1; // 1 to N-3
            if (numL > 6) numL = 6;
            var numR = amountVertex-2-numL;
            
            iVL = {};
            iEL = {};
            amountEdge = 0;
        
            iVL[0] = {
              "x": 50,
              "y": 175,
            }
        
            iVL[amountVertex-1] = {
              "x": 650,
              "y": 175,
            }
        
            for (var i = 1; i <= numL; i++) {
              iVL[i] = {
                "x": 250,
                "y": (175 + (i - (numL+1)/2) * (numL == 1 ? 0 : 300/(numL-1))),
              }
              iEL[amountEdge] = {
                "u": 0,
                "v": i,
                "w": 1
              }
              if (randomType == 0 || randomType == 2)
                iEL[amountEdge]["w"] = 1+Math.floor(Math.random()*9);
              amountEdge++;
            }
        
            for (var i = 1; i <= numR; i++) {
              iVL[i+numL] = {
                "x": 450,
                "y": (175 + (i - (numR+1)/2) * (numR == 1 ? 0 : 300/(numR-1))),
              }
              iEL[amountEdge] = {
                "u": i+numL,
                "v": amountVertex-1,
                "w": 1
              }
              if (randomType == 0 || randomType == 1)
                iEL[amountEdge]["w"] = 1+Math.floor(Math.random()*9);
              amountEdge++;
            }
        
            for (var i = 1; i <= numL; i++) {
              for (var j = 1; j <= numR; j++) {
                var existEdge = Math.floor(Math.random()*2);
                if (existEdge == 1) {
                  iEL[amountEdge] = {
                    "u": i,
                    "v": j+numL,
                    "w": 9
                  }
                  amountEdge++;
                }
              }
            }
        
            amountVertex = 0;
            amountEdge = 0;
            for (var i in iVL) amountVertex++;
            for (var i in iEL) amountEdge++;
            var newState = createState(iVL, iEL);
            gw.updateGraph(newState, 500);
        
            $('#sourcevertex').val(0);
            $('#sinkvertex').val(amountVertex-1);
            return true;
          }
        
          function createState(iVLObject, iELObject, vertexHighlighted, edgeRed, vertexTraversed, edgeYellow, edgeBlue, edgeGrey) {
            if (vertexHighlighted == null) vertexHighlighted = {};
            if (edgeRed == null) edgeRed = {};
            if (vertexTraversed == null) vertexTraversed = {};
            if (edgeYellow == null) edgeYellow = {};
            if (edgeBlue == null) edgeBlue = {};
            if (edgeGrey == null) edgeGrey = {};
        
            var key;
            var state = {
              "vl":{},
              "el":{}
            };
        
            for (key in iVLObject) {
              state["vl"][key] = {};
              state["vl"][key]["cx"] = iVLObject[key]["x"];
              state["vl"][key]["cy"] = iVLObject[key]["y"];
              if (iVLObject[key]["text"] == null)
                state["vl"][key]["text"] = +key;
              else
                state["vl"][key]["text"] = iVLObject[key]["text"];
              if (iVLObject[key]["state"] == OBJ_HIDDEN)
                state["vl"][key]["state"] = OBJ_HIDDEN;
              else
                state["vl"][key]["state"] = VERTEX_DEFAULT;
              state["vl"][key]["extratext"] = iVLObject[key]["extratext"];
            }
        
            for (key in iELObject) {
              state["el"][key] = {};
              state["el"][key]["vertexA"] = iELObject[key]["u"];
              state["el"][key]["vertexB"] = iELObject[key]["v"];
              state["el"][key]["type"] = EDGE_TYPE_DE;
              state["el"][key]["weight"] = iELObject[key]["w"];
              if (iELObject[key]["state"] == OBJ_HIDDEN)
                state["el"][key]["state"] = OBJ_HIDDEN;
              else
                state["el"][key]["state"] = EDGE_DEFAULT;
              state["el"][key]["displayWeight"] = true;
              state["el"][key]["animateHighlighted"] = false;
            }
        
            for (key in vertexHighlighted)
              state["vl"][key]["state"] = VERTEX_HIGHLIGHTED;
        
            for (key in edgeRed)
              state["el"][key]["state"] = EDGE_RED;
        
            for (key in vertexTraversed)
              state["vl"][key]["state"] = VERTEX_TRAVERSED;
        
            for (key in edgeYellow)
              state["el"][key]["state"] = EDGE_TRAVERSED;
        
            for (key in edgeBlue)
              state["el"][key]["state"] = EDGE_BLUE;
        
            for (key in edgeGrey)
              state["el"][key]["state"] = EDGE_GREY;
        
            return state;
          }
          
          function populatePseudocode(act) {
            switch (act) {
              case 0: // Edmonds Karp
                // $('#code1').html('initMaxFlow');
                // $('#code2').html('while there is an augmenting path');
                // $('#code3').html('&nbsp;&nbsp;find an augmenting path using BFS');
                // $('#code4').html('&nbsp;&nbsp;for each edge u->v in the path');
                // $('#code5').html('&nbsp;&nbsp;&nbsp;&nbsp;decrease capacity u->v by bottleneck');
                // $('#code6').html('&nbsp;&nbsp;&nbsp;&nbsp;increase capacity v->u by bottleneck');
                // $('#code7').html('&nbsp;&nbsp;increase maxflow by bottleneck');
                $('#code1').html('initMaxFlow');
                $('#code2').html('while there is an augmenting path');
                $('#code3').html('&nbsp;&nbsp;find an augmenting path using BFS');
                $('#code4').html('&nbsp;&nbsp;for each edge u-&gt;v in the path');
                $('#code5').html('&nbsp;&nbsp;&nbsp;&nbsp;decrease capacity u-&gt;v by bottleneck');
                $('#code6').html('&nbsp;&nbsp;&nbsp;&nbsp;increase capacity v-&gt;u by bottleneck');
                $('#code7').html('&nbsp;&nbsp;increase maxflow by bottleneck');
                break;
              case 1: // Ford Fulkerson
                // $('#code1').html('initMaxFlow');
                // $('#code2').html('while there is an augmenting path');
                // $('#code3').html('&nbsp;&nbsp;find an augmenting path using DFS');
                // $('#code4').html('&nbsp;&nbsp;for each edge u->v in the path');
                // $('#code5').html('&nbsp;&nbsp;&nbsp;&nbsp;decrease capacity u->v by bottleneck');
                // $('#code6').html('&nbsp;&nbsp;&nbsp;&nbsp;increase capacity v->u by bottleneck');
                // $('#code7').html('&nbsp;&nbsp;increase maxflow by bottleneck');
                $('#code1').html('initMaxFlow');
                $('#code2').html('while there is an augmenting path');
                $('#code3').html('&nbsp;&nbsp;find an augmenting path using DFS');
                $('#code4').html('&nbsp;&nbsp;for each edge u-&gt;v in the path');
                $('#code5').html('&nbsp;&nbsp;&nbsp;&nbsp;decrease capacity u-&gt;v by bottleneck');
                $('#code6').html('&nbsp;&nbsp;&nbsp;&nbsp;increase capacity v-&gt;u by bottleneck');
                $('#code7').html('&nbsp;&nbsp;increase maxflow by bottleneck');
                break;
              case 2: // Dinic
                // $('#code1').html('initMaxFlow');
                // $('#code2').html('while t is reachable from s in the residual graph');
                // $('#code3').html('&nbsp;&nbsp;find the level graph (BFS)');
                // $('#code4').html('&nbsp;&nbsp;for each blocking flow in the level graph (DFS)');
                // $('#code5').html('&nbsp;&nbsp;&nbsp;&nbsp;update the capacity in the blocking flow');
                // $('#code6').html('&nbsp;&nbsp;&nbsp;&nbsp;increase maxflow by bottleneck');
                // $('#code7').html('');
                $('#code1').html('initMaxFlow');
                $('#code2').html('while t is reachable from s in the residual graph');
                $('#code3').html('&nbsp;&nbsp;find the level graph (BFS)');
                $('#code4').html('&nbsp;&nbsp;for each blocking flow in the level graph (DFS)');
                $('#code5').html('&nbsp;&nbsp;&nbsp;&nbsp;update the capacity in the blocking flow');
                $('#code6').html('&nbsp;&nbsp;&nbsp;&nbsp;increase maxflow by bottleneck');
                $('#code7').html('');
                break;
              case 3: // Rook Attack Modeling
                // $('#code1').html('Create source and sink vertex');
                // $('#code2').html('Create one vertex Ri for each row i');
                // $('#code3').html('Create one vertex Cj for each column j');
                // $('#code4').html('For each rook-placable cell (i,j)');
                // $('#code5').html('&nbsp;&nbsp;Add an edge from Ri to Cj with capacity INF');
                // $('#code6').html('Run any maxflow algorithm');
                $('#code1').html('Create source and sink vertex');
                $('#code2').html('Create one vertex Ri for each row i');
                $('#code3').html('Create one vertex Cj for each column j');
                $('#code4').html('For each rook-placable cell (i,j)');
                $('#code5').html('&nbsp;&nbsp;Add an edge from Ri to Cj with capacity INF');
                $('#code6').html('Run any maxflow algorithm');
                $('#code7').html('');
                break;
              case 4: // Baseball Elimination Modeling
                // $('#code1').html('Checking for obvious cases');
                // $('#code2').html('For every team X,Y');
                // $('#code3').html('&nbsp;&nbsp;Create XvY vertex. Connect source to the vertex');
                // $('#code4').html('For every team X');
                // $('#code5').html('&nbsp;&nbsp;Create TX vertex. Connect the vertex to sink');
                // $('#code6').html('Connect XvY vertex to TX and TY with capacity INF');
                // $('#code7').html('Run any maxflow algorithm');
                $('#code1').html('Checking for obvious cases');
                $('#code2').html('For every team X,Y');
                $('#code3').html('&nbsp;&nbsp;Create XvY vertex. Connect source to the vertex');
                $('#code4').html('For every team X');
                $('#code5').html('&nbsp;&nbsp;Create TX vertex. Connect the vertex to sink');
                $('#code6').html('Connect XvY vertex to TX and TY with capacity INF');
                $('#code7').html('Run any maxflow algorithm');
                break;
            }
          }
        }
        
        
        
        // MaxFlow_action.js
        var actionsWidth = 150;
        var statusCodetraceWidth = 410;
        
        var isModelingOpen = false, isExamplesOpen = false, isCountMaximumFlowOpen = false;
        
        function openModeling() {
          //$(".modeling").css("bottom","150px");
          $('#rookattack-input').hide();
          $('#baseball-input').hide();
          $('#bipartite-input').hide();
          if (!isModelingOpen) {
            $('.modeling').fadeIn('fast');
            isModelingOpen = true;
          }
        }
        
        function closeModeling() {
          if (isModelingOpen) {
            $('.modeling').fadeOut('fast');
            $('#modeling-err').html("");
            isModelingOpen = false;
          }
        }
        
        function openExamples() {
          if (!isExamplesOpen) {
            $('.examples').fadeIn('fast');
            isExamplesOpen = true;
          }
        }
        
        function closeExamples() {
          if (isExamplesOpen) {
            $('.examples').fadeOut('fast');
            isExamplesOpen = false;
          }
        }
        
        function openCountMaximumFlow() {
          if (!isCountMaximumFlowOpen) {
            $('.countmaxflow').fadeIn('fast');
            $('#countmaxflow-go').show();
            $('#countmaxflow-algorithm').hide();
            isCountMaximumFlowOpen = true;
          }
        }
        
        function closeCountMaximumFlow() {
          if (isCountMaximumFlowOpen) {
            $('.countmaxflow').fadeOut('fast');
            $('#countmaxflow-err').html("");
            isCountMaximumFlowOpen = false;
          }
        }
        
        function hideEntireActionsPanel() {
          closeModeling();
          closeExamples();
          closeCountMaximumFlow();
          hideActionsPanel();
        }
        
        
        
        // local
        var mfw, gw, randomGraphID = -1;
        
        $(function() {
          write(false, false);
          $('#play').hide();
          mfw = new MaxFlow();
          gw = mfw.getGraphWidget();
          var options = [CP3_4_24, CP3_4_26_1, CP3_4_26_2, CP3_4_26_3, FORDFULKERSON_KILLER, DINIC_SHOWCASE];
          mfw.examples(options[Math.floor(Math.random()*6)]);
          randomGraphID = -1;
        
          var graphJSON = getQueryVariable("create");
          if (graphJSON.length > 0) {
            importjson(graphJSON);
            window.history.pushState("object or string", "Title", window.location.href.split('?')[0]);
          }
        
          $('#modeling').click(function() {
            openModeling();
            closeExamples();
            closeCountMaximumFlow();
          });
        
          $('#examples').click(function() {
            closeModeling();
            openExamples();
            closeCountMaximumFlow();
          });
        
          $('#countmaxflow').click(function() {
            closeModeling();
            closeExamples();
            openCountMaximumFlow();
          });
        });
        
        function importjson(text) {
          if (isPlaying) stop();
          if (mode == "exploration") {
            mfw.importjson(text);
            closeExamples();
            isPlaying = false;
          }
        }
        
        function drawGraph() {
          if (isPlaying) stop();
          if (mode == "exploration") {
            $('#dark-overlay').fadeIn(function() {
              $('#drawgraph').fadeIn();
            });
            mfw.startLoop();
            isPlaying = false;
          }
        }
          
        function drawDone() {
          if (!mfw.draw()) return false;
          mfw.stopLoop();
          $('#drawgraph').fadeOut();
          $('#dark-overlay').fadeOut();
        }
        
        function drawCancel() {
          mfw.stopLoop();
          $('#drawgraph').fadeOut();
          $('#dark-overlay').fadeOut();
        }
        
        function bipartiteRandom(randomType) {
          mfw.bipartiteRandom(randomType);
        }
        
        function createRandom() {
          if (isPlaying) stop();
          if (mode == "exploration") {
            var n = Math.floor(5 + Math.random()*6);
            $.ajax({
              url: PHP_DOMAIN + "/php/Graph.php?mode=" + MODE_GET_RANDOM_SUBMITTED_GRAPH + "&directed=" + 1 + "&connected=" + 1
            }).done(function(data){
              data = JSON.parse(data);
              var graph = extractQnGraph(data.graph);
              if (data.graphID == randomGraphID) // make sure it is different, make sure #graph > 1
                createRandom();
              randomGraphID = data.graphID;
              mfw.initRandom(graph);
              $('#rate-sample-graph').show();
            })
            $('#progress-bar').slider( "option", "max", 0);
            closeExamples();
            isPlaying = false;
          }
        }
        
        function modelingOpen(modelingType) {
          //$(".modeling").css("bottom","117px");
          if (modelingType != "rookattack") $('#rookattack-input').fadeOut('fast');
          if (modelingType != "baseball")   $('#baseball-input').fadeOut('fast');
          if (modelingType != "bipartite")  $('#bipartite-input').fadeOut('fast');
          $('#' + modelingType + '-input').fadeIn('fast');
        }
        
        function modeling(modelingType) {
          if (isPlaying) stop();
          setTimeout(function() {
            if (mode != "exploration") return;
            if (!mfw.modeling(modelingType)) return;
          }, 500);
        }
        
        function example(id) {
          if (isPlaying) stop();
          setTimeout(function() {
            if ((mode == "exploration") && mfw.examples(id)) {
              $('#progress-bar').slider( "option", "max", 0);
              closeExamples();
              closeCountMaximumFlow();
              isPlaying = false;
            }
          }, 500);
        }
        
        function countmaxflow(algorithm) {
          if (algorithm == 'GO') {
            $('#countmaxflow-go').hide();
            $('#countmaxflow-algorithm').fadeIn('fast');
            return;
          }
          if (isPlaying) stop();
          var source = parseInt($('#sourcevertex').val());
          var sink = parseInt($('#sinkvertex').val());
          setTimeout( function()  {
            if (mode != "exploration") return;
            if (!mfw.countmaxflow(algorithm,source,sink)) return;
            $('#current-action').show();
            if (algorithm == "edmondskarp")
              $('#current-action p').html("Edmonds Karp(" + source + "," + sink + ")");
            if (algorithm == "fordfulkerson")
              $('#current-action p').html("Ford Fulkerson(" + source + "," + sink + ")");
            if (algorithm == "dinic")
              $('#current-action p').html("Dinic(" + source + "," + sink + ")");
            $('#progress-bar').slider( "option", "max", gw.getTotalIteration()-1);
            triggerRightPanels();
            isPlaying = true;
          }, 500);
        }
        </script>
  
</body>

</html>